package madixin.t198;

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map<Integer, Integer> map = new HashMap<>();

    //rob[i]=max(rob[i-2] + nums[i] , rob[i-1])
    public int rob(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return 0;
        }
        return rob(nums, nums.length);
    }

    private int rob(int[] nums, int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return nums[0];
        }
        int res = 0;
        if (map.containsKey(n)) {
            res = map.get(n);
        } else {
            res = Math.max(rob(nums, n - 2) + nums[n - 1], rob(nums, n - 1));
            map.put(n, res);
        }
        return res;
    }

    public int rob2(int[] nums) {
        int pre2 = 0, pre1 = 0;
        for (int i = 0; i < nums.length; i++) {
            int cur = Math.max(pre2 + nums[i], pre1);
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}